googologywikiaorg-20200223-history
User blog:Vel!/Symbols function
This is my stab at the idea of a "symbols function," like the ones used in Rayo's number and Ikosarakt's blog. Before I launch into defining my own, I'm going to explain what a symbols function exactly is. Let \(\Lambda\) denote a finite set of symbols. Define a string \(S\) to be a list containing a finite number of \(\Lambda\) symbols, and call a parser \(\Pi(S)\) be a function mapping strings to positive integers. The symbols function of \(\Pi\) is a function \(\Psi : \mathbb{N} \rightarrow \mathbb{N}\). \(\Psi(n)\) is the smallest positive integer such that there does not exist a string \(S\) with at most \(n\) symbols such that \(\Pi(S) = n\). Informally, this means that we create a language that defines numbers. If we put a cap on the number of symbols we're allowed to use, what's the biggest number we can define? (Equivalently, what's the smallest number we can't define?) What's the most beautiful story we can tell with only three words? Ink, Rope, Rose The "function" part of symbols functions is already done for us. The trick is to define \(\Lambda\) and \(\Pi\) (the "language") in the most elegant way possible — that is, with only a bare minimum of symbols, all with definitions that make mathematical sense. It's a bit like taking a story and writing a language for it. My attempt at reaching this goal only uses three symbols: * + (increment, "ink") * [ (recursion open, "rope") * ] (recursion close, "rose") Taking from their Bowersesque nicknames, I call my system Ink, Rope, Rose or IRR. Formally, it is defined by the following: * "" = 1 * "+" = 2 * "+n" = "n" + 1 * "n" = "n" * "nm" = "nnn...nnn", "m" times In plain English: * There is an implicit "1" at the end of a string. * Ink is a unary successor operator. An expression preceded by + is incremented by 1. ** Thus, a string containing only inks becomes its length plus one. "+++++" = 6, "+++++++" = 7, etc. All IRR strings decompose into strings of inks. * An expression s'' enclosed in rope and rose, followed by a number ''n, solves to s'' repeated ''n times. If n'' is not specified, the implicit "1" is used, giving the identity "n" = "n". Here are some examples of IRR in action: * "+++++" = 6 * "++++++++++" = 11 * "+++" = "+++" = 4 * "++++++" = "+++" repeated "+++" times = "+++" repeated 4 times = "+++ +++ +++ +++" = 13 * "++++++++" = "+++++ +++++ +++++ +++++" = 21 * "+++++++" = "+ +++ +++ +++ +++" = 14 * "+++" = "+++" = "+++" = 4 * "++++++" = "+++" repeated 4 times = "++++++++++++" ** = "++++++++++++" ** = "++++++ +++ +++ +++ +++" ** = "+++ (13 copies of +++)" ** = "40 copies of +++" ** = 121 * "[+++]+++" = "++++++++++++" = "++++++++++++" = ... IRR vs. arrow notation IRR constructions are similar to Knuth arrows. Here's why: * "ab" = \(a(b + 1) + 1 > ab\) (>~ meaning "greater than, but still comparable to") * "ab" = "aa...aa" > \(a^b\) * "[a]b" > \(a\uparrow\uparrow b\) * "[[a]]b" > \(a\uparrow\uparrow\uparrow b\) To me, this looks like we're somewhere in the \(f_\omega\) range in the fast-growing hierarchy. I have no mathematical explanation for this; it's just a gut feeling. To extend the system, we need a way of diagonalizing the [[a]] notation — that is, allowing repetition of [] commands. ''To be continued... The symbols function :Disclaimer: I have not checked these calculations; they are probably wrong. So what does the symbols function look like? For the first few steps, rope and rose aren't efficient enough, so ink overtakes them: * s(1) = "+" = 2 * s(2) = "++" = 3 * s(3) = "+++" = 4 * s(4) = "++++" = 5 * s(5) = "+++++" = 6 * s(6) = "++++++" = 7 Starting with s(7), things change: * s(7) = "+++++" = "+++ +++ +++" = 10 * s(8) = "++++" = "++++++" = "++ ++ ++ ++" = "++ ++ ++ ++ ++ ++ ++" = 15 * s(9) = "+++++" = "+++++++++" = "+++ +++ +++ +++ +++" = "+++ +++ +++ +++ +++ +++ +++ +++ +++ +++ +++ +++ +++" = 40 My guess is that it grows pretty rapidly from here, but I haven't invested the time to make the calculations by computer. Since rope-rose pairs correspond to different levels of arrow notation, s(n) is a distant relative of \(f_\omega(n)\) in FGN. The next level What next? We could allow the brackets themselves to repeat. Perhaps a second level of brackets is in order, like "<[>n" = n copies of "[". But that can't get very far, since we can just keep defining new levels of brackets like "{<}" and "({)". Eventually our system becomes a salad because we have to stop the brackets at an arbitrary point. (Our types of brackets can't be infinite, either — \(\Lambda\) is always a finite collection of symbols.) What we need is a way of picking a particular level of bracket within IRR itself. One of the first things I noticed after publishing IRR is that rope is unnecessary. At least within the context of symbols functions, doing something like "++++++++" is a waste of precious characters, since we can just move the leading ink to the end. Category:Blog posts